package com.yuting.practice;

import java.util.ArrayList;
import java.util.List;

/**
 * 很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不 同。例如有的金矿储量是500kg黄金，需要5个工人来挖掘；
 * 有的金矿储量是200kg黄金，需要3个工人 来挖掘…… 如果参与挖矿的工人的总数是10。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。
 * 要求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
 */
public class Grab {


    public static void main(String[] args) {
        List<Mime> mimes = new ArrayList<>();
        Mime mime1 = new Mime(500,5);
        Mime mime2 = new Mime(400,4);
        Mime mime3 = new Mime(880,8);
        Mime mime4 = new Mime(100,2);
        Mime mime5 = new Mime(700,6);

        mimes.add(mime1);
        mimes.add(mime2);
        mimes.add(mime3);
        mimes.add(mime4);
        mimes.add(mime5);

        List<Mime> choose = choose(mimes, 10);

        System.out.println(choose);

    }


    public static List<Mime> choose(List<Mime> mimes, int persons){

        System.out.println("size"+mimes.size());
        int[][] dp = new int[mimes.size() + 1][persons + 1];

        for (int i = 1; i <= dp.length - 1; i++){

            for(int j = 1; j <= dp[0].length - 1; j++){

                Mime tmp = mimes.get(i - 1);
                if(j >= tmp.getNeed()){

                    dp[i][j] = Math.max(dp[i - 1][j - tmp.getNeed()] + tmp.getAmount(), dp[i - 1][j]);

                }else {
                    dp[i][j] = dp[i - 1][j];
                }

            }

        }

        System.out.println(dp[mimes.size()][persons]);

        //倒推出选的mines
        List<Mime> result = new ArrayList<>();
        int j = persons;

        for(int i = mimes.size(); i > 0; i--){
            if(dp[i][j] > dp[i - 1][j]){
                result.add(mimes.get(i - 1));
                j = j - mimes.get(i - 1).getNeed();
            }


            if(j <= 0){
                break;
            }
        }



        return result;
    }


    static class Mime{

        private int amount;

        private int need;

        public Mime(int amount, int need) {
            this.amount = amount;
            this.need = need;
        }

        public int getAmount() {
            return amount;
        }

        public void setAmount(int amount) {
            this.amount = amount;
        }

        public int getNeed() {
            return need;
        }

        public void setNeed(int need) {
            this.need = need;
        }

        @Override
        public String toString() {
            return "Mime{" +
                    "amount=" + amount +
                    ", need=" + need +
                    '}';
        }
    }

}
